The present invention relates in general to computer animation techniques. More particularly, embodiments the present invention relate to a system and a method for efficiently rendering objects with ray tracing where the objects are geometrically grouped and the rays are geometrically grouped according to directions of travel of the rays.
Throughout the years, movie makers have often tried to tell stories involving make-believe creatures, far away places, and fantastic things. To do so, they have often relied on animation techniques to bring the make-believe to “life.” Two of the major paths in animation have traditionally included drawing-based animation techniques and stop motion animation techniques.
Drawing-based animation techniques were refined in the twentieth century, by movie makers such as Walt Disney and used in movies such as “Snow White and the Seven Dwarfs” (1937) and “Fantasia” (1940). This animation technique typically required artists to hand-draw or paint animated images onto transparent media or cels. After painting, each cel would then be captured or recorded onto film as one or more frames in a movie.
Stop motion-based animation techniques typically required the construction of miniature sets, props, and characters. The filmmakers would construct the sets, add props, and position the miniature characters in a pose. After the animator was happy with how everything was arranged, one or more frames of film would be taken of that specific arrangement. Stop motion animation techniques were developed by movie makers such as Willis O'Brien for movies such as “King Kong” (1933). Subsequently, these techniques were refined by animators such as Ray Harryhausen for movies including “Mighty Joe Young” (1948) and “Clash Of The Titans” (1981).
With the wide-spread availability of computers in the later part of the twentieth century, animators began to rely upon computers to assist in the animation process. This included using computers to facilitate drawing-based animation, for example, by painting images, by generating in-between images (“tweening”), and the like. This also included using computers to augment stop motion animation techniques. For example, physical models could be represented by virtual models in computer memory, and manipulated.
One of the pioneering companies in the computer graphics (CG) industry was Pixar. Pixar developed both computing platforms specially designed for CG, and rendering software now known as RENDERMAN®. RENDERMAN® was particularly well received in the CG industry and was recognized with two Academy Awards®. RENDERMAN® software is used to convert graphical specifications of objects and convert them into one or more images. This technique is known generally in the industry as rendering.
One CG technique used for image rendering (or rendering) is ray tracing. Ray tracing is an image rendering technique where computerized rays (or rays) are projected from a “camera” (i.e., the viewpoint of an imaginary viewer) through pixels in the image plane and outward toward a computerized scene (or scene). Ray tracing contrasts with other inefficient image rendering techniques, such as where rays might be traced from a light source to a scene and then to the camera. Tracing rays from the camera outward provides orders of magnitude higher computing efficiency in rendering a scene as compared to tracing rays from a light source to the camera as many rays that originate at a light source either do not reach the camera or do not significantly contribute to a rendered image of a scene.
According to traditional ray tracing techniques, a determination is made for each ray whether the ray intersects a computerized object (or object) in a scene. As referred to herein a scene may include one or more objects, which may be computerized light sources (or light sources) or objects with which light interacts. If a ray does not intersect an object, the pixel associated with the ray may be shaded according to a background color or the like.
More specifically, when rendering an object for a scene using ray tracing, primary rays are traced and a determination is made whether the rays intersect an object. The primary rays are used to determine the portions of the object that are visible or in shadow. If a point on an object is visible, the point is shaded to indicate its visibility, and if a point is in shadow, the point is alternatively shaded to indicate shadow. Secondary rays, tertiary rays, etc., which are respectively associated with the primary rays, are then traced to determine reflection from the object, shadow, ambient occlusion, refraction through the object, color of the object, and/or the like.
One disadvantage associated with traditional ray tracing is that objects are be accessed in memory in an arbitrary order because each secondary ray could potentially hit any object anywhere in a scene. A relatively simplistic ray tracing scheme typically considers “n” number of objects for each primary ray, secondary ray, tertiary ray, etc. To consider n objects in a ray tracing scheme, the objects are accessed from memory in an arbitrary order as discussed above, which results in relatively slow processing. Processing acceleration schemes have been developed to help with this memory access problem, such as storing the objects in a three dimensional tree structure according to the bounding boxes of the objects. While this technique accelerates the determination of the objects that are considered for a ray intersection test, it is still necessary to retrieve these objects from memory. Because memory access is not performed in a coherent order, each object in a scene usually is read in from memory in an inefficient manner. If the number of objects in a scene is relatively large, this can be very expensive in term of processing time and hence monetary expense.
As can therefore be understood from the foregoing description, traditional ray tracing techniques have limited ability to efficiently render an image. Therefore, it is highly desirable to provide more efficient techniques for ray tracing.